package com.qfedu.entity.course17;

public class StringMatch {
    public static int bf(String s, String t) {
        int pos = -1;
        for (int i = 0; i < s.length() - t.length() + 1; i++) {
            if (s.charAt(i) == t.charAt(0)) {
                int jc = 0;
                for (int j = 0; j < t.length(); j++) {
                    if (s.charAt(i + j) != t.charAt(j)) {
                        break;
                    }
                    jc = j;
                }
                if (jc == t.length() - 1) {
                    pos = i;
                    return pos;
                }
            }
        }
        return pos;
    }

    public static int bf2(String s, String t) {
        for (int i = 0; i < (s.length() - t.length() + 1); i++) {
            if (s.substring(i, i + s.length()).equals(t)) {
                return i;
            }
        }
        return -1;
    }

    public static int RKalth(String s, String t) {
        int tHash = strToHash(t);
        for (int i = 0; i < s.length() - t.length() + 1; i++) {
            if (tHash == strToHash(s.substring(i, i + t.length()))) {
                return i;
            }
        }
        return -1;
    }

    /*** 支持 a-z 二十六进制 * 获得字符串的hash值 * @param src * @return */
    public static int strToHash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash *= 26;
            hash += str.charAt(i) - 97;
        }
        return hash;
    }


    /**
     * 坏字符
     *
     * @param s 主串
     * @param t 模式串
     * @return
     */
    public static int BMalthBad(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        //主串长度
        int m = sChars.length;
        //模式串长度
        int n = tChars.length;
        //创建字典
        int[] bc = new int[256];
        // 构建坏字符哈希表，记录模式串中每个字符最后出现的位置
        generateBC(tChars, bc);
        // i表示主串与模式串对齐的第一个字符
        int i = 0;
        while (i <= m - n) {
            int j;
            for (j = n - 1; j >= 0; --j) {
                // 模式串从后往前匹配
                // i+j ：不匹配的位置
                if (sChars[i + j] != tChars[j]) {
                    // 坏字符对应模式串中的下标是j
                    break;
                }
            }
            if (j < 0) {
                // 匹配成功，返回主串与模式串第一个匹配的字符的位置
                return i;
            }
            // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
            // j：si bc[(int)a[i+j]]:xi
            i = i + (j - bc[(int) sChars[i + j]]);
        }
        return -1;
    }

    /**
     * @param b
     * @param dc
     */
    private static void generateBC(char[] b, int[] dc) {
        for (int i = 0; i < 256; ++i) {
            // 初始化 bc 模式串中没有的字符值都是-1
            dc[i] = -1;
        }
        //将模式串中的字符希写入到字典中
        for (int i = 0; i < b.length; ++i) {
            // 计算 b[i] 的 ASCII 值
            int ascii = (int) b[i];
            dc[ascii] = i;
        }
    }

    public static void main(String[] args) {
        System.out.println(bf2("beijitestbeijingok", "beijing"));
    }
}
